class Solution
{
public:
    // 和周赛316的题差不多，完全暴力会超时，稍微暴力就能过
    int subarrayLCM(vector<int> &nums, int k)
    {
        int count = 0;
        int n = nums.size();
        for (int i = 0; i < n; ++i)
        {
            int _lcm = nums[i];
            int j = i;
            while (j < n)
            {
                _lcm = lcm(_lcm, nums[j]);
                if (_lcm == k)
                {
                    ++count;
                }
                else if (_lcm > k || k % _lcm != 0)
                {
                    break;
                }
            }
        }
        return count;
    }

    int subarrayLCM(vector<int> &nums, int k)
    {
        int count = 0;
        int n = nums.size();
        for (int i = 0; i < n; ++i)
        {
            for (int j = i; j < n; ++j)
            {
                int _lcm = nums[i];
                for (int m = i; m <= j; ++m)
                {
                    _lcm = lcm(_lcm, nums[m]);
                    if (_lcm > k)
                    {
                        break;
                    }
                }
                if (_lcm == k)
                {
                    ++count;
                }
            }
        }
        return count;
    }
};